package com.brett.frame.learn.sort.insert;

/**
 * 直接插入排序
 * 依次取待排序列的值，插入到已有序列合适位置。
 * @author lenovo
 *
 */
public class DirectInsertSort {

	public int[] sort(int[] arr) {

		for (int i = 1; i < arr.length; i++) {
			if (arr[i - 1] > arr[i]) {
				int tmp = arr[i];// 使用临时变量，减少交换次数
				int j = i - 1;
				for (; j >= 0 && arr[j] > tmp; j--) {
					arr[j + 1] = arr[j];
				}
				arr[j + 1] = tmp;
			}
		}
		return arr;
	}
}
